1. Field of the Invention
The present invention relates to a three-dimensional (3D) graphics, and more particularly, to a method for and/or an apparatus for high-speed visualization of a depth image-based 3D graphic data.
2. Description of the Related Art
Initially, the ultimate goal of 3D graphics is to synthesize realistic graphic images with equal realism compared with the real world. Conventionally, a polygonal mesh is widely used in 3D computer graphics to represent a 3D object, with which any arbitrary shape of object can be modeled properly. Due to the advances in a graphics algorithm and a graphics processing unit (GPU), even very complex objects or scenes can be rendered in real-time.
Recently, mobile devices such as a cellular phone and a personal digital assistant (PDA) have become very popular. In addition, attempts are made to provide a multimedia services, such as graphics animation, moving pictures, music, and games. Furthermore, there have been attempts to show 3D graphics objects on the mobile devices in such applications.
However, unlike typical personal computers, there have been severe problems in attempting to apply 3D graphics to a mobile device. First, the CPUs usually don't have enough processing power. Second, the mobile CPUs do not support floating-point arithmetic operations. Third, the mobile CPUs also don't have hardware 3D graphics accelerators either. For these reasons, it is very difficult to render 3D object at an interactive frame rate on mobile devices.
On the other hand, efficient methods for representing and visualizing a 3D object without use of explicit mesh representation have recently been introduced. One such method is called depth image-based representation (DIBR), which has been adopted as an international standard in MPEG-4 animation framework extension (AFX), as detailed in “Coding of Audio-Visual Objects: Animation Framework Extension (AFX)”, ISO/IEC JTC1/SC29/WG11 14496-16. It is similar to the relief texture discussed in “Relief textures mapping,” Proc. SIGGRAPH '00, pp. 359-368, July 2000. However, DIBR is more intuitive and has better structure for fast rendering using 3D warping.
In the DIBR method, the present inventors proposed a fast rendering algorithm of Simple Texture format of DIBR, which is a set of reference images covering visible surfaces of the 3D object, discussed in “Depth image-based representations for static and animated 3D objects,” Proc. IEEE International Conference on Image Processing, vol. III, pp. 25-28, Rochester, USA, September 2002. Here, each reference image consists of a texture (color) image and a corresponding depth image, in which each pixel value denotes the distances from the image plane to the surface of the object. A depth image-based model (DIBM) has advantages in that the reference image can provide high quality visualization for an object without directly using the aforementioned complex polygonal meshes. Furthermore, the rendering complexity for synthesizing a new scene is proportional to the number of pixels, not to the complexity of the scene. This feature is useful in rendering on mobile devices that usually have low display resolution. According to the DIBM, a 3D object is represented by texture and depth images, observed by N cameras where N is an arbitrary integer. An example of the DIBR is shown in FIG. 1.
A point texture and an octree image are different formats of the DIBR family. In the point texture, an object is represented by an array of pixels observed at one camera position as shown in FIG. 2. Each point texture pixel is represented by a color, a depth corresponding to a distance from a pixel to the camera, and several properties contributing to the point texture visualization. There may be a plurality of pixels in each intersection between each line of sight and an object. Therefore, the point texture is typically organized with multiple layers. In the octree image, an object is represented by using an octree, as shown in FIGS. 3A and 3B, with images on each side being used as reference images.
Another method has been introduced, where a warping algorithm is capable of producing a visualized view from a new view point without accomplishing a depth test, (hereinafter referred to as the McMillan method) discussed in “An image-based approach to three-dimensional computer graphics,” L. McMillan, PhD Dissertation, University of North Carolina at Chapel Hill, 1997. Now, the McMillan's method will be described in more detail. As shown in FIG. 4, a world coordinate system is organized according to geometric information of the reference images. For example, a point P1 on the reference coordinate system is transformed into a point P2 on the world coordinate system. From the new view point, the point P2 is viewed as a point P3. The point P3 is obtained by applying a transformation matrix T to the point P1. In order to align points of the reference image on a new view point, an epipolar point is searched. The epipolar point corresponds to a center of a new view (that is, a center of a new camera view) projected to the reference image. Moreover, to which of nine regions, shown in FIG. 5, the epipolar point is projected is identified, and then a splatting order of the pixels on the reference image is determined according to a sign on a z-axis. If a sequential visualization is performed such that pixels are projected one by one to a new view along rows and columns of a grid array according to the order determined as described above, the depth test becomes unnecessary because the latest mapped pixel always occupies the closest point.
Meanwhile, a further attempt to expand the concept of the depth image has been suggested, with a layered depth image method, in which multiple pixels correspond to one pixel position. This method is disclosed in “Layered depth images”, Proc. of SIGGRAPH '98, pp. 231-242, July 1998. In a simple depth image, distortion occurs in an object surface where data do not exist while a view point changes. On the contrary, in the layered depth image, such distortion does not occur because even an invisible back surface of an object has 3D coordinate information and composes the layered depth image. The visualization method of the layered depth image is nearly similar to the McMillan algorithm. Specifically, a direction and an order of drawing pixels in a new image is determined according to the position of the epipolar point on the reference image of the new view and a sign on a z-axis as shown in FIG. 5. According to this method, a back-to-front visualization can be always obtained without the depth test.
On the other hand, in the fields of portable apparatuses, there has not been sufficient research in such high-speed visualization of a 3D graphic object by using the image-based representation.